home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Collection of Tools & Utilities
/
Collection of Tools and Utilities.iso
/
edit
/
tde40.zip
/
findrep.c
< prev
next >
Wrap
C/C++ Source or Header
|
1994-06-05
|
52KB
|
1,712 lines
/******************* start of original comments ********************/
/*
* Written by Douglas Thomson (1989/1990)
*
* This source code is released into the public domain.
*/
/*
* Name: dte - Doug's Text Editor program - find/replace module
* Purpose: This file contains the functions relating to finding text
* and replacing text.
* It also contains the code for moving the cursor to various
* other positions in the file.
* File: findrep.c
* Author: Douglas Thomson
* System: this file is intended to be system-independent
* Date: October 1, 1989
*/
/********************* end of original comments ********************/
/*
* The search and replace routines have been EXTENSIVELY rewritten. The
* "brute force" search algorithm has been replaced by the Boyer-Moore
* string search algorithm. This search algorithm really speeds up search
* and replace operations.
*
* Sketch of the BM pattern matching algorithm:
*
* while (not found) {
* fast skip loop; <=== does most of the work and should be FAST
* slow match loop; <=== standard "brute force" string compare
* if (found) then
* break;
* shift function; <=== mismatch, shift and go to fast skip loop
* }
*
* See:
*
* Robert S. Boyer and J Strother Moore, "A fast string searching
* algorithm." _Communications of the ACM_ 20 (No. 10): 762-772, 1977.
*
* See also:
*
* Zvi Galil, "On Improving the Worst Case Running Time of the Boyer-
* Moore String Matching Algorithm." _Communications of the ACM_
* 22 (No. 9): 505-508, 1979.
*
* R. Nigel Horspool, "Practical fast searching in strings." _Software-
* Practice and Experience_ 10 (No. 3): 501-506, 1980.
*
* Alberto Apostolico and Raffaele Giancarlo, "The Boyer-Moore-Galil
* String Searching Strategies Revisited." _SIAM Journal on Computing_
* 15 (No. 1): 98-105, 1986.
*
* Andrew Hume and Daniel Sunday, "Fast String Searching." _Software-
* Practice and Experience_ 21 (No. 11): 1221-1248, November 1991.
*
* Timo Raita, "Tuning the Boyer-Moore-Horspool String Searching Algorithm."
* _Software-Practice and Experience_ 22 (No. 10): 879-884, October 1992.
*
*
* Boyer-Moore in TDE
*
* Hume and Sunday demonstrated in their paper that using a simple shift
* function after a mismatch gives one of the fastest search times with the
* Boyer-Moore algorithm. When searching normal text for small patterns
* (patterns less than 30 characters or so), Hume and Sunday found that the
* faster the algorithm can get back into the fast skip loop with the
* largest shift value then the faster the search. Some algorithms can
* generate a large shift value, but they can't get back into the skip loop
* very fast. Hume and Sunday give a simple method for computing a shift
* constant that, more often than not, is equal to the length of the search
* pattern. They refer to the constant as mini-Sunday delta2 or md2. From
* the end of the string, md2 is the first leftmost occurrence of the
* rightmost character. Hume and Sunday also found that using a simple string
* compare as the match function gave better performance than using the C
* library memcmp( ) function. The average number of compares in the slow
* loop was slightly above 1. Calling the memcmp( ) function to compare 1
* character slows down the algorithm. See the Hume and Sunday paper for an
* excellent discussion on fast string searching. Incidentally, Hume and
* Sunday describe an even faster, tuned Boyer-Moore search function.
*
* The Boyer-Moore search algorithm in TDE was rearranged so that it is now
* almost identical to the original version Boyer-Moore described in CACM.
* The simple shift function in TDE was replaced by the mini-delta2 shift
* function in the Hume and Sunday paper.
*
* I am not very fond of WordStar/TURBO x style search and replace prompting,
* which is used in the DTE 5.1 editor. Once the search pattern has been
* defined, one only needs to press a key to search forwards or backwards.
* The forward or backward search key may be pressed at any time in any file
* once the pattern has been entered. Also, the search case may be toggled
* at any time in any file once the pattern has been entered.
*
* Thanks to Tom Waters, twaters@relay.nswc.navy.mil, for finding a bug when
* building the ignore skip index array in TDE 1.3 and previous versions.
* BTW, I added assertions to those functions that build the skip index
* array to make certain that everything is everything.
*
* Thanks also to David Merrill, u09606@uicvm.uic.edu, for recommending a
* change and the source code for the solution to what can be an annoying
* feature in the find function. Pressing <FindForward> before defining
* the pattern would cause TDE to display an error message. Since we already
* know that the search pattern is undefined, we can easily prompt for
* the search pattern. I usually tolerate such features until I get tired
* of being annoyed with error messages and finally write a solution.
* Dave, thanks for the solution and the easy-to-implement code. Although
* such changes are small, they really make for a more comfortable editor.
*
* New editor name: TDE, the Thomson-Davis Editor.
* Author: Frank Davis
* Date: June 5, 1991, version 1.0
* Date: July 29, 1991, version 1.1
* Date: October 5, 1991, version 1.2
* Date: January 20, 1992, version 1.3
* Date: February 17, 1992, version 1.4
* Date: April 1, 1992, version 1.5
* Date: June 5, 1992, version 2.0
* Date: October 31, 1992, version 2.1
* Date: April 1, 1993, version 2.2
* Date: June 5, 1993, version 3.0
* Date: August 29, 1993, version 3.1
* Date: November 13, 1993, version 3.2
* Date: June 5, 1994, version 4.0
*
* This modification of Douglas Thomson's code is released into the
* public domain, Frank Davis. You may distribute it freely.
*/
#include "tdestr.h"
#include "common.h"
#include "tdefunc.h"
#include "define.h"
/*
* Name: get_replacement_flags
* Purpose: To input find and replace flags.
* Date: June 5, 1991
* Modified: November 13, 1993, Frank Davis per Byrial Jensen
* Passed: line: prompt line
* Returns: OK if flags were entered, ERROR if user wanted to abort
*/
int get_replacement_flags( int line )
{
register int c;
int func;
int rc;
#if defined( __UNIX__ )
chtype display_buff[MAX_COLS+2]; /* chtype is defined in curses.h */
#else
char display_buff[(MAX_COLS+2)*2];
#endif
save_screen_line( 0, line, display_buff );
eol_clear( 0, line, g_display.text_color );
/*
* options: prompt or no prompt (p/n)?
*/
s_output( find1, line, 0, g_display.message_color );
xygoto( strlen( find1 ) + 2, line );
do {
c = getanswerkey( );
func = getfunc( c );
} while (c != L_PROMPT && c != L_NO_PROMPT &&
c != RTURN && c != ESC && func != AbortCommand);
restore_screen_line( 0, line, display_buff );
switch (c) {
case L_PROMPT :
case RTURN :
g_status.replace_flag = PROMPT;
rc = OK;
break;
case L_NO_PROMPT :
g_status.replace_flag = NOPROMPT;
rc = OK;
break;
default :
rc = ERROR;
}
bm.search_defined = rc;
return( rc );
}
/*
* Name: ask_replace
* Purpose: Ask user if he wants to (r)place, (s)kip, or (e)xit.
* Date: June 5, 1991
* Modified: November 13, 1993, Frank Davis per Byrial Jensen
* Returns: TRUE if user wants to replace, ERROR otherwise.
* Passed: window: pointer to current window
* finished: TRUE if user pressed ESC or (e)xit.
*/
int ask_replace( TDE_WIN *window, int *finished )
{
regist